package it.storm.solution;

import java.util.Arrays;

/**
 * 1275. 找出井字棋的获胜者
 * https://leetcode-cn.com/problems/find-winner-on-a-tic-tac-toe-game/
 */
public class Solutions_1275 {
    public static void main(String[] args) {
//        int[][] moves = {{0, 0}, {2, 0}, {1, 1}, {2, 1}, {2, 2}};  // output: "A"
//        int[][] moves = {{0, 0}, {1, 1}, {0, 1}, {0, 2}, {1, 0}, {2, 0}};  // output: "B"
        int[][] moves = {{0, 0}, {1, 1}, {2, 0}, {1, 0}, {1, 2},
                {2, 1}, {0, 1}, {0, 2}, {2, 2}};  // output: "Draw"
//        int[][] moves = {{0, 0}, {1, 1}};  // output: "Pending"

        String result = tictactoe(moves);
        System.out.println(result);
    }

    /**
     * 解法二：枚举法
     * 1. 根据 moves 填充棋盘
     * 2. 只有 8 种情况下，能够获胜
     */
    public static String tictactoe(int[][] moves) {
        int len = moves.length;
        if (len < 5) {
            // 未满 5 个棋子时，不会有胜者
            return "Pending";
        }
        // 填充棋盘
        char[][] board = new char[3][3];
        for (char[] row : board) {
            Arrays.fill(row, '.');
        }
        boolean isA = true;
        for (int[] move : moves) {
            board[move[0]][move[1]] = isA ? 'X' : 'O';
            // 下一步，该 B 下（轮流落子）
            isA = !isA;
        }
        // 判断 A 是否胜利
        if (Win(board, 'X')) {
            return "A";
        }
        // 判断 B 是否胜利
        if (Win(board, 'O')) {
            return "B";
        }
        // 没有胜者，判断是否平局（即已经全部落子，但是没有产生胜者）
        return len == 9 ? "Draw" : "Pending";
    }

    public static boolean Win(char[][] board, char c) {
        return  // 三行
           (board[0][0] == board[0][1] && board[0][1] == board[0][2] && board[0][2] == c)
        || (board[1][0] == board[1][1] && board[1][1] == board[1][2] && board[1][2] == c)
        || (board[2][0] == board[2][1] && board[2][1] == board[2][2] && board[2][2] == c)
                // 三列
        || (board[0][0] == board[1][0] && board[1][0] == board[2][0] && board[2][0] == c)
        || (board[0][1] == board[1][1] && board[1][1] == board[2][1] && board[2][1] == c)
        || (board[0][2] == board[1][2] && board[1][2] == board[2][2] && board[2][2] == c)
               // 两条对角线
        || (board[0][0] == board[1][1] && board[1][1] == board[2][2] && board[2][2] == c)
        || (board[0][2] == board[1][1] && board[1][1] == board[2][0] && board[2][0] == c);
    }

    /**
     * 解法一
     * 1. 根据最后落子的坐标来确定胜者（若有胜利者，那么最后落子后导致获胜，并游戏结束）
     * 2. 没有胜者的情况下，判断是平局还是游戏未结束
     */
    public static String tictactoe2(int[][] moves) {
        int len = moves.length;
        if (len < 5) {
            // 未满 5 个棋子时，不会有胜者
            return "Pending";
        }
        int rowCount = 0;  // 该行上与其相同棋子的数量
        int colCount = 0;  // 该列上与其相同棋子的数量
        int mainDiagonal = 0;  // 主对角线上与其相同棋子的数量
        int secondDiagonal = 0;  // 副对角线上与其相同棋子的数量

        // 主对角线特征：[0, 0], [1, 1], [2, 2]，x == y
        // 副对角线特征：[0, 2], [1, 1], [2, 0]，x + y == 2
        // 最后一个子的行坐标与列坐标
        int rowLoc = moves[len - 1][0];
        int colLoc = moves[len - 1][1];
        for (int i = len - 1; i >= 0; i -= 2) {
            if (moves[i][0] == rowLoc) {
                // 在同一行时，计数
                rowCount ++;
            }
            if (moves[i][1] == colLoc) {
                // 在同一列时，计数
                colCount ++;
            }
            if (rowLoc == colLoc && moves[i][0] == moves[i][1]) {
                // 同在主对角线时，计数
                mainDiagonal ++;
            }
            if (rowLoc + colLoc == 2 && moves[i][0] + moves[i][1] == 2) {
                // 同在副对角线时，计数
                secondDiagonal ++;
            }
        }
        if (rowCount == 3 || colCount == 3 || mainDiagonal == 3 ||
            secondDiagonal == 3) {
            // 说明一定有胜利者，且胜利者就是最后落子的棋手（因为获胜后，游戏结束）
            // 从 1 计数时，偶数长度的胜利者是 B，奇数长度的胜利者是 A
            return moves.length % 2 == 0 ? "B" : "A";
        }
        // 没有胜利者时，根据落子的数量，可分为 "Draw" 和 "Pending" 两种情况
        return len == 9 ? "Draw" : "Pending";
    }
}
